package 滑动窗口;

import java.util.HashMap;
import java.util.Map;

public class 最小覆盖子串 {
    public static void main(String[] args) {
        String s="ADOBECODEBANC";
        String t="ABC";
        System.out.println(minWindow(s, t));
    }

    public static String minWindow(String s, String t) {
        Map<Character, Integer>  window=new HashMap<>();
        Map<Character, Integer>  need=new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            need.put(t.charAt(i),need.getOrDefault(t.charAt(i),0)+1);
        }
        int left=0,right=0;
        int vaild=0;
        int start=0;
        int len=Integer.MAX_VALUE;
        while (right<s.length()){
            char c = s.charAt(right);
            //窗口右移
            right++;
            if (need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                if (need.get(c)==window.get(c))
                    vaild++;
            }
            //判断窗口是否要压缩
            while (vaild==need.size()){
                //更新最小覆盖子串
                if (right-left<len){
                    start=left;
                    len=right-left;
                }
                //缩小窗口
                char d = s.charAt(left);
                left++;
                if (need.containsKey(d)){
                    if (window.get(d).equals(need.get(d)))
                        vaild--;
                    window.put(d, window.getOrDefault(d, 0) - 1);
                }
            }
        }
        return len==Integer.MAX_VALUE?"":s.substring(start,len+start);
    }
}
